package linkedlist.leetcode_143_medium;

public class ReOrderList {
    public void reOrderList(ListNode head){
        if(head == null || head.next == null || head.next.next == null){
            return;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode newHead = reverse(slow.next);

        while(head != null && newHead != null){
            ListNode temp1 = head.next;
            ListNode temp2 = newHead.next;
            head.next = newHead;
            newHead.next = temp1;
            head = temp1;
            newHead = temp2;
        }
    }
    public ListNode reverse(ListNode head){
        ListNode temp = null;
        ListNode pre = null;
        while(head != null){
            temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}
